﻿//前K个高频单词(medium): https://leetcode.cn/problems/top-k-frequent-words/
class Solution {
public:
    typedef pair<string,int> PIS;
    struct Cmp
    {
        bool operator()(PIS p1,PIS p2)
        {
            return p1.second>p2.second||(p1.second==p2.second&&p1.first<p2.first);
        }
    };
    vector<string> topKFrequent(vector<string>& words, int k) {
        priority_queue<PIS,vector<PIS>,Cmp> heap;
        unordered_map<string,int> hash;
        for(auto& x:words)
        {
            hash[x]++;
        }
        for(auto& x:hash)
        {
            heap.push(x);
            if(heap.size()>k)  heap.pop();
        }
        vector<string> ret;
        while(heap.size())
        {
            PIS out=heap.top();
            ret.push_back(out.first);
            heap.pop();
        }
        reverse(ret.begin(),ret.end());
        return ret;
    }
};